package tencent.music;

/**
 * @author habitplus
 * @problem
 * @desc
 * @link
 * @since 2021-08-26 22:26
 */
public class T20210826N3 {
    public int fillWays(int[] arr, int k) {
        if (arr == null || arr.length < 1 || k < 1) {
            return 0;
        }
        final int mod = 1000000007;
        long ans = 1;
        int preIdx = -1;
        int n = arr.length, cZeroCnt, numCnt;
        long t;
        for (int i = 0; i <= n; i++) {
            if (i == n || arr[i] != 0) {
                // 当前的数不是要删除的数

                cZeroCnt = i - preIdx - 1;
                if (cZeroCnt > 0) {
                    numCnt = (i == n ? k : arr[i]) + 1 - (preIdx == -1 ? 1 : arr[preIdx]);
                    t = ((long) Math.pow(numCnt, cZeroCnt) - numCnt) / 2 + numCnt;
                    t = t % mod;
                    ans = (ans * t) % mod;
                }
                preIdx = i;
            }
        }

        return (int) ans;
    }

    public static void main(String[] args) {
        final int mod = (int) Math.pow(10, 9) + 7;

        System.out.println(new T20210826N3().fillWays(new int[]{0,0,0, 4, 0}, 6));
    }
}
